#include <iostream>
using namespace std;
// TIP 要<b>Run</b>代码，请按 <shortcut actionId="Run"/> 或点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。


long long gcdll(long long a, long long b){
    if (a < 0) a = -a;                // 分子可能为负
    while (b) { long long t = a % b; a = b; b = t; }
    return a;
}

int func2() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin >> T)) return 0;
    while (T--) {
        long long a,b,c,d;
        cin >> a >> b >> c >> d;

        long long num = 1LL*a*d + 1LL*c*b;  // 分子
        long long den = 1LL*b*d;            // 分母(>0)

        long long g = gcdll(num, den);
        den /= g;                            // 只关心最简分母

        while (den % 2 == 0) den /= 2;
        while (den % 5 == 0) den /= 5;

        cout << (den == 1 ? "YES" : "NO") << '\n';
    }
    return 0;
}
int func1() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    for (int i = 0; i < m; i++) {
        string op;
        cin >> op;
        int pos = 0;
        // 提取括号里的数字
        for (char c : op) {
            if (isdigit(c)) {
                pos = pos * 10 + (c - '0');
            }
        }

        if (op.find("toLowerCase") != string::npos) {
            s[pos] = tolower(s[pos]);
        } else {
            s[pos] = toupper(s[pos]);
        }
    }

    cout << s << "\n";
    return 0;
}


int func() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        // 按余数类分组
        vector<vector<long long>> groups(m);
        for (int i = 0; i < n; i++) {
            groups[i % m].push_back(a[i]);
        }

        // 每个组内排序
        for (int r = 0; r < m; r++) {
            sort(groups[r].begin(), groups[r].end());
        }

        // 回填：依次取组内最小的数填回原数组
        vector<long long> ans(n);
        vector<int> idx(m, 0); // 记录每个组已经取了多少个
        for (int i = 0; i < n; i++) {
            int r = i % m;
            ans[i] = groups[r][idx[r]++];
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            cout << ans[i] << (i + 1 == n ? '\n' : ' ');
        }
    }

    return 0;
}